1. Field of the Invention
The present invention generally relates to retrieval of data records. More specifically, the present invention relates to a system, method and apparatus for performing parallel lookups of data records each associated with a frame in a stream of frames, where the lookups keep the order of frames accessing the same data records.
2. Discussion of the Related Art
In networking applications, frames of data are sent through a network. The frames may contain data and reference additional data. Networking applications often utilize Transmission Control Protocol (TCP) to transmit and receive the frames. Frames are packets of information that may be transferred on a network, such as a computer network.
A single device in a TCP protocol implementation can have many xe2x80x9cconversationsxe2x80x9d (TCP connections) with other devices occurring simultaneously. When a device on the network receives a frame, a conversation-identifier is extracted from IP (Internet Protocol) and TCP headers in the frame. The conversation-identifier may be a xe2x80x9ckey.xe2x80x9d A key is piece or data, or code, that references a section of data. For example, a frame may be sent with the key xe2x80x9c1010xe2x80x9d. The key xe2x80x9c1010xe2x80x9d may reference a xe2x80x9cstatus recordxe2x80x9d for one of the TCP conversations, for example, in a memory. The status record is used by the TCP protocol to process the frame.
There are several methods in the art for locating a key in a memory. For example, a hash-based method has been used. In a hash-based method, there are a set number of look-up engines. Each lookup engine may be a separate program, or a subroutine in a program, for example, that searches for keys in a memory. Many systems in the art utilize more than one lookup engine to search for keys in the memory. The systems typically allocate keys to one of the plurality of lookup engines based upon certain calculations. For example, the hashing method creates a hash value for each key and, based upon the hash value, assigns the key to one of the lookup engines. An exemplary hash-based embodiment may include two lookup engines, A and B, and use keys comprised of four digits. The hash function may be set to sum the digits of the key and send all keys with even-number hash values to lookup engine A and all keys with odd-number hash values to lookup engine B. For example, the sum of the digits in the key xe2x80x9c1010xe2x80x9d yields an even number, and would therefore be assigned to lookup engine A. The sum of the digits of key xe2x80x9c1011xe2x80x9d yields an odd number, and would therefore be assigned to lookup engine B. However, a hash-based method is inefficient in a situation where two keys yield the same even (or odd) hash value. In such a situation, one of the lookup engines remains idle while the second key waits until the lookup engine for even hash values locates the first key. Then, the second key may be allocated to the even hash value lookup engine.
Another method for finding keys utilizes a distribution calculation in link aggregation. The distribution calculation in link aggregation is similar to the hash-based method, except that keys for frames are distributed to a number of network links, rather than to a number of lookup engines. The distribution calculation suffers from shortcomings similar to those of the hash-based method, because the system once again searches for the keys based upon the results of a calculation.
The order of processing of frames may matter, for example, in situations where two frames have the same key, and therefore access the same set of data in the memory. If the data is subject to change by virtue of it being accessed, then the first frame must be processed before the second frame is processed.
The order of processing of frames may also matter if a routing protocol is being used that requires frames to be processed in the order in which they are received. An additional reason why the order of processing of the frames may matter is because TCP processing of frames is faster/better when frames for a given conversation are processed by a device in the same order in which that they were generated by the other device. Usually the network does not reorder frames, so by processing frames in the order they are received, they are thereby usually processed in the order they were generated.
In many embodiments in the art, lookups typically take a constant amount of time. The lookups ordinarily complete in the order in which they were initiated, so no specific action has to be taken to ensure the order. However, a problem with this type of lookup is that the usable lookup engines are limited because they always have to use the same low number of memory access to perform the lookup. In another method where the order matters, lookups may take a variable amount of time. However, in the current state of the art, such lookups are performed one-at-a-time.
Accordingly, the systems in the prior art are inefficient in looking up frames where the order of the lookups matters. Prior systems either utilize multiple lookups engines that each search for a set length of time, or search for a variable length of time using one lookup engine at a time. Therefore, systems in the prior art cannot perform multiple lookups for variable lengths of time simultaneously.